Tree Traversals: The Three Paths

PolyU DSAI2201 • Lecture 13 • 2025-11-25

Depth First Search (DFS) Traversals

Tree traversals are the methods used to visit every node in the tree exactly once. The three main Depth First Search (DFS) traversals are differentiated solely by when the Root (R) node is processed relative to its Left (L) and Right (R) children.

Traversal NameOrder (L/R/R)Execution Principle (Recursive)Primary Use Case
1. Pre-orderR, L, RVisit Root, then traverse Left subtree, then traverse Right subtree.Creating a prefix expression (Polish Notation), Copying a tree.
2. In-orderL, R, RTraverse Left subtree, visit Root, then traverse Right subtree.Retrieving elements of a Binary Search Tree (BST) in sorted order.
3. Post-orderL, R, RTraverse Left subtree, then traverse Right subtree, then visit Root.Deleting a tree, evaluating expression trees (Postfix/Reverse Polish Notation).

Traversal Algorithm Complexity

Since every node $N$ in the tree must be visited exactly once regardless of the traversal path, the time complexity remains consistent.

MetricComplexityRationale
Time Complexity$O(N)$$N$ is the number of nodes. Each node is processed once.
Space Complexity$O(H)$$H$ is the height of the tree. Represents the maximum depth of the recursive call stack. $H$ can be $O(\log N)$ (balanced) or $O(N)$ (skewed).
📝 Interactive Quiz

1. What is the correct In-order Traversal sequence for the tree below?

graph TD A(10) --> B(5) A --> C(15) B --> D(3) B --> E(7)
  • A) 10, 5, 3, 7, 15
  • B) 3, 5, 7, 10, 15
  • C) 3, 7, 5, 15, 10
  • D) 5, 3, 7, 10, 15

2. Using the same tree, what is the correct Pre-order Traversal sequence?

  • A) 10, 5, 3, 7, 15
  • B) 3, 5, 7, 10, 15
  • C) 3, 7, 5, 15, 10
  • D) 10, 15, 5, 7, 3

3. And what is the correct Post-order Traversal sequence for that tree?

  • A) 10, 5, 3, 7, 15
  • B) 3, 5, 7, 10, 15
  • C) 3, 7, 5, 15, 10
  • D) 15, 7, 3, 5, 10

4. Which traversal is required to print the nodes of a Binary Search Tree (BST) in ascending sorted order?

  • A) Pre-order
  • B) In-order
  • C) Post-order
  • D) Level-order